package cn.edu.xjtu.work.majorityElement;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 169. 多数元素
 * 
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 */
public class Solution {
  public static void main(String[] args) {
    int[] nums = new int[] { 2, 2, 1, 1, 1, 2, 2 };
    majorityElement(nums);
  }

  /**
   * Boyer-Moore 投票算法
   * 
   * @param nums
   * @return
   */
  public static int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
      if (count == 0) {
        candidate = nums[i];
        count++;
      } else if (candidate == nums[i]) {
        count++;
      } else {
        count--;
      }
    }
    return candidate;
  }

  /**
   * 哈希表
   * 
   * @param nums
   * @return
   */
  public static int majorityElement1(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i : nums) {
      map.put(i, map.getOrDefault(i, 0) + 1);
    }

    for (Integer i : map.keySet()) {
      if (map.get(i) > nums.length / 2) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 排序,由于多数元素时超过二分之一的元素,因此一定在排序过后数组的中位数处
   * 
   * @param nums
   * @return
   */
  public static int majorityElement2(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
  }
}
